
//
// Created by madison on 2022/7/25.
//

#include "vector"
#include "math.h"

using namespace std;

class Solution {
public:
    // 方法一：动态规划
    int climbStairs(int n) {
        int p, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    // 递归写法
    int climbStairs1(int n) {
        if (n <= 1) {
            return 1;
        }
        if (n < 3) {
            return n;
        }
        return climbStairs1(n - 1) + climbStairs1(n - 2);
    }

    int climbStairs2(int n) {
        if (n <= 1) {
            return 1;
        }
        vector<int> dp = {0, 1, 2};
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 方法三：通项公式
    int climbStairs3(int n) {
        double sqrt5 = sqrt(5);
        double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);
        return (int) round(fibn / sqrt5);
    }
};

int main() {
    Solution solution;
    printf("%d", solution.climbStairs3(5));
    return 0;
}